// https://www.lintcode.com/problem/longest-increasing-subsequence/my-submissions

// 注意对比
// Basis/Algorithm/动态规划/longest-continuous-increasing-subsequence.cpp

class Solution {
public:
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    // int longestIncreasingSubsequence(vector<int> &nums) {
    //     if (nums.empty()) return 0;
    //     int n = nums.size();
    //     vector<int> res(n, 1);
    //     int maxRes = 1;
    //     for (int i = 1; i < n; ++i)
    //     {
    //         for (int j = 0; j < i; ++j)
    //         {
    //             if (nums[j] < nums[i])
    //             {
    //                 res[i] = max(res[i], res[j] + 1); 
    //             }
    //         }
    //         maxRes = max(maxRes, res[i]);
    //     }
    //     // return res.back(); 注意不是最后的答案
    //     // int maxRes = 1; 可以放到过程中去
    //     // for (int i = 0; i < n; ++i)
    //     // {
    //     //     if (res[i] > maxRes)
    //     //         maxRes = res[i];
    //     // }
    //     return maxRes;
    // }
    
    // 优化：• 每个f[j]都在寻找前面比自己小的a[i]里，最大的f[i]
    // • 对于每个f值:1, 2, ..., 记录当前为止拥有这个f值的最小的a[i]
    //  一个新的数a[j]来了，它的f值很好算:在序列中找到最后一个比它小的数a[i]，f[j] 就是 f[i] + 1
    // 然后用a[j]替换序列中的a[i]的下一个，因为f[j]和它值一样，但a[j]更小
// • 在序列(a[1]=1, a[6]=2, a[5]=3)中找到最后一个比它小的数a[i]，f[j] 就是 f[i] + 1
// • 而序列永远是单调增的
// • 所以可以二分查找
// • 序列长度<=N，因此最长上升子序列长度<=N
// • 每次查找时间复杂度O(log2N)
// • 总的时间复杂度O(Nlog2N)
// f: 0 1 2 3 4 5
// a: -inf 10 20 30 ...
// rec: rec[i]: smallest a value such that its f value is i
    int longestIncreasingSubsequence(vector<int> &nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        vector<int> rec;
        rec.push_back(INT_MIN);
        for (int i = 0; i < n; ++i)
        {
            int start = 0;
            int end = rec.size() - 1;
            while (start + 1 < end)
            {
                int mid = (end - start) / 2 + start;
                if (rec[mid] < nums[i])
                {
                    start = mid;
                }
                else
                {
                    end = mid;
                }
            }
            if (rec[end] < nums[i])
            {
                if (end + 1 < rec.size())
                    rec[end + 1] = nums[i];
                else
                    rec.push_back(nums[i]);
            }
            else
            {
                rec[start + 1] = nums[i];
            }
        }
        return rec.size() - 1;
    }
};